package lc.数学问题;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/11/3
 */
public class 剑指Offer39_数组中出现次数超过一半的数字 {

    public int majorityElement(int[] nums) {
        // 假如我们有个职位，需要从 A，B 两位候选人中选出
        //先抽出一张票，投的是 A，我们在黑板上写着当前胜利者：A，票数：1
        //再抽出一张票，投的是 A，我们在黑板上写着当前胜利者：A，票数：2
        //再抽出一张票，投的是 B，用一张 B 抵消一张 A 的选票，我们在黑板上写着当前胜利者：A，票数：1
        //再抽出一张票，投的是 B，用一张 B 抵消一张 A 的选票，我们在黑板上写着当前胜利者：无，票数：0
        //再抽出一张票，投的是 A，我们在黑板上写着当前胜利者：A，票数：1
        //抽取完毕，恭喜 A 获胜，赢得该职位。
        int res = 0, count = 0;
        for (int num : nums) {
            if (count == 0) res = num;
            count += (res == num) ? 1 : -1;
        }
        return res;
    }
}
